#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        for (int i = n; i >= 0; i--)
        {
            string num = to_string(i);
            //int flag = 0;
            int j;
            for (j = 1; j < num.size(); j++)
            {
                if (num[j] < num[j - 1])
                {
                    break;
                }
            }
            if (j == num.size())
                return i;
        }
        return 0;
    }
};

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        for (int i = n; i >= 0; i--)
        {
            int tmp = i;
            int prev = tmp % 10;
            int cur = 9;
            while (tmp && prev <= cur)
            {
                cur = prev;
                tmp /= 10;
                if (i == 1234)
                    cout << tmp << endl;
                prev = tmp % 10;
            }
            if (tmp == 0)
                return i;
        }
        return 0;
    }
};

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string tmp = to_string(n);
        int left = 0;
        for (int i = 0; i < tmp.size() - 1; i++)
        {
            if (tmp[i] > tmp[i + 1])
            {
                while (i - 1 >= 0 && tmp[i - 1] == tmp[i])
                {
                    i--;
                }
                tmp[i++]--;

                for (; i < tmp.size(); i++)
                    tmp[i] = '9';
                break;
            }
        }
        int ret = 0;
        for (auto e : tmp)
        {
            ret *= 10;
            ret += e - '0';
        }
        return ret;
    }
};

class Solution {
public:
    int brokenCalc(int startValue, int target) {
        int begin = startValue;
        int end = target;
        if (end <= begin)
            return begin - end;
        else
        {
            int step = 0;
            while (end > begin)
            {
                if (end % 2 == 1)
                {
                    end++;
                }
                else
                    end /= 2;
                step++;
            }
            step += begin - end;
            return step;
        }
    }
};
class Solution {
public:
    struct Com
    {
        bool operator()(const vector<int>& l, const vector<int>& r)
        {
            return l[0] < r[0];
        }
    };
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int m = intervals.size();
        vector<vector<int>> ret;
        Com com;
        sort(intervals.begin(), intervals.end(), com);
        ret.push_back(intervals[0]);
        int j = 0;
        for (int i = 1; i < m; i++)
        {
            if (intervals[i][0] <= ret[j][1])
            {
                ret[j][0] = min(ret[j][0], intervals[i][0]);
                ret[j][1] = max(ret[j][1], intervals[i][1]);
            }
            else
            {
                ret.push_back(intervals[i]);
                j++;
            }
        }
        return ret;
    }
};

class Solution {
public:
    struct Com
    {
        bool operator()(const vector<int>& l, const vector<int>& r)
        {
            return l[0] == r[0] ? l[1] < r[1] : l[0] < r[0];
        }
    };
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        Com com;
        sort(intervals.begin(), intervals.end(), com);
        int m = intervals.size();
        //int left = 0;
        int ret = 0;
        int left = intervals[0][0];
        int right = intervals[0][1];
        for (int i = 1; i < m; i++)
        {
            if (intervals[i][0] == left)
            {
                ret++;
            }
            else if (intervals[i][0] >= right)
            {
                left = intervals[i][0];
                right = intervals[i][1];
            }
            else if (intervals[i][0] < right)
            {
                if (intervals[i][1] < right)
                {
                    ret++;
                    right = intervals[i][1];
                    left = intervals[i][0];
                }
                else
                    ret++;
            }
        }
        return ret;
    }
};
